前言

昨天提到說明了

• DHT便是將傳統的Hash Bucket變成一個個實體的Node

• 而Consistent Hashing是將Key與Node都一起Hash到同一個Hash Space，並將Data存到最近的Node裡面。

  • 最主要解決的就是 Monotonicity 特性
  • 加入與刪除一個Node並不需要重新分配所有的Data

舉例:

• 將Key Hash到[0,1]內的一個值
• 將Node Hash一樣到[0,1]內的一個值
• 將Data存到往右邊看最近的Node

• 也因此，當我們將一個新的Node N4加入，我們不需要重新分配Data，而是只需要更新[N2,N4]範圍內的Data會重新分配到N4中

以上就是 Consistent Hashing 的精神
但是目前這樣的做法有一個小問題，那就是對於[N3,1]之間的Data應該存在哪呢?

一種很直觀的方法就是將[0,1]區間變成一個 環狀！

而 CHORD 演算法就是基於這樣的一個環狀Hash Space設計自己的Routing方法。

CHORD

簡介

CHORD是一個由MIT在2001年發表的一種DHT演算法。

作為一個Library，提供DHT給上層的 authentication、caching、replication、naming 等應用。
而CHORD的興起在於他非常簡單就可以實作。

開源網址在這裡: https://github.com/sit/dht/
裡面還包含了很多其餘相關的open source project，例如Merkle Tree

實作

Hash

基於 Consistent Hashing 的想法，

• Hash Space為一個m-bit的ID-Space，串聯成一個環
• 一般使用 SHA-1 作為Hash Function
• SHA-1(IP address) 得到 NodeID
• SHA-1(Key) 得到KeyID

如下圖所示，Keys與Nodes都會在同一個環上，我們將Data存入順時鐘方向最接近的Node上面。

幾個重點

• 例如: K10的Data存入Node N14
• Hash Function可以做到平均分散資料的儲存
  • 每一個Node儲存**O(K/N)**個Key
  • 因此當有Node的增加或是移除時，只需要移動**O(K/N)**個Keys

Lookup(Key)

1. Basic CHORD

每一個Node只會記錄兩個Neighbors

1. 下一個Node => Successor
2. 前一個Node => Predecessor

當一個Client連上某個Node希望找尋某個Data時，
若是該Node沒有該Data，便將請求傳遞給Successor。

舉例:

上面的m=7，就是假設Hash出來的ID為一個7bits的ID
一般採用SHA-1會是 160its

此種方法的缺點也很直觀，就是Worst Case會繞整個環一圈
因此時間複雜度會是O(N)

有沒有方法可以改善呢？

2. CHORD with Finger Table

• Define

我們改成每一個Node可以記錄m個Neighbors，形成一個Finger Table來做Lookup，

定義:
Finger i 指向 n+2^i i=0~m-1 共m個點，
而n是目前的Node

如下圖舉例:

對於Node n12來說，其Finger Table定義如下
m=7, n=12

• Lookup 方法

當Node記錄了上面的Finger Table，在搜尋目標Data時，就可以將原本的O(N)降為O(lgN)。

如下圖

1. Client連上Node N12要尋找Key Hash出來為100的Data
2. N12沒有，因此從他認識的Neighbors問起
3. 透過Finger Table知道，最接近ID=100的，為自己記錄的ID=76對應的Node N80
4. 因此N12->N80將請求傳遞給N80
5. N80也沒有，但是透過Finger Table知道ID=100的資料跟自己有記錄的ID=99很接近，應該都是屬於Node N110的
6. N80->N110將請求傳遞給N110，而N110回應有Data
7. 一路傳回來後Client就知道要連上Node N110來下載資料

這樣的Routing法可以將複雜度降到O(lgN)

為什麼呢?以下粗淺不專業的類比一下
從ID用m-bit表示
與Finger Table記錄的m個Node是每次增加2^i
你可以發現他每次都會嘗試找最接近的，而且是以2的次方在接近
就變成與二分搜的概念一樣
當然也就是O(lgN)
這個幾乎也是所有DHT演算法降時間複雜度的手段

小結

以上就是DHT CHORD的Lookup介紹，明天會來介紹CHORD如何處理Data Partitioning與DHT的另外一個難題，也就是新增與刪除一個Node，如何重新分配那O(K/N)的Node。

Reference:

• TU Dresde System Engineering I&II - P2P Network